public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().backspaceCompare("ab#c", "ad#c"));
        System.out.println(new Solution().backspaceCompare("#cab###", "er##ger#####cc#d##"));
        System.out.println(new Solution().backspaceCompare("a#c", "b"));
    }
}

//二刷
class Solution3 {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        while (i >= 0 || j >= 0) {
            int backspaceCountS = 0;
            while (i >= 0 && (s.charAt(i) == '#' || backspaceCountS > 0)) {
                if (s.charAt(i) == '#') {
                    backspaceCountS++;
                } else {
                    backspaceCountS--;
                }
                i--;
            }

            int backspaceCountT = 0;
            while (j >= 0 && (t.charAt(j) == '#' || backspaceCountT > 0)) {
                if (t.charAt(j) == '#') {
                    backspaceCountT++;
                } else {
                    backspaceCountT--;
                }
                j--;
            }

            if (i < 0 && j < 0) {
                return true;
            }
            if (i < 0 || j < 0) {
                return false;
            }
            if (s.charAt(i) != t.charAt(j)) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}

//从后往前遍历
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int skipS = 0, skipT = 0;
        int sI = s.length() - 1, tI = t.length() - 1;
        while (sI >= 0 || tI >= 0) {
            while (sI >= 0 && (skipS > 0 || s.charAt(sI) == '#')) {
                if (s.charAt(sI) == '#') {
                    skipS++;
                } else {
                    skipS--;
                }
                sI--;
            }
            while (tI >= 0 && (skipT > 0 || t.charAt(tI) == '#')) {
                if (t.charAt(tI) == '#') {
                    skipT++;
                } else {
                    skipT--;
                }
                tI--;
            }
            if (sI < 0 || tI < 0) {
                return sI < 0 && tI < 0;
            }
            if (s.charAt(sI) != t.charAt(tI)) {
                return false;
            }
            sI--; tI--;
        }
        return true;
    }
}


//从前往后还原出字符串
class Solution1 {
    public boolean backspaceCompare(String s, String t) {
        return getResult(s).equals(getResult(t));
    }


    String getResult(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#') {
                if (sb.length() > 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
                continue;
            }
            sb.append(c);
        }
        return sb.toString();
    }
}